/**
 * LeetCode20：有效的括号
 * 给定一个只包括"(,),[,],{,}"的字符串
 * 判断该字符串是否有效
 * 字符串有效的条件：1.左括号必须用相同类型的右括号闭合 2.左括号必须以正确的顺序闭合
 *
 */

/**
 *
 * @param {String} s
 * @return {Boolean}
 */
var isValid = function (s){
    //字符串长度为奇数时，一定是不符合条件的，加入判断以优化性能
    if (s.length % 2 === 1){return false;}
    let flag = true;
    const stack = [];
    const map = new Map();
    map.set("(",")");
    map.set("[","]");
    map.set("{","}");
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (map.get(c)){
            stack.push(c);
        }else {
            //考虑到传入的字符串可能为"())"，执行到最后一个右括号时，
            //stack长度为0，获取stack[-1]，在js里会返回undefined，在其他语言中可能会抛出异常
            if (stack.length === 0){
                flag = false;
                return false;
            }else {
                const t = stack[stack.length-1];
                if (map.get(t) === c){
                    stack.pop();
                }else {
                    flag = false;
                    return false;
                }
            }
        }
    }
    return flag;
}

//时间复杂度：O(n)
//空间复杂度：O(n)